We present the earliest results of our NACO/VLT sparse aperture masking (SAM) campaign to search for binarity in a sample of 60 O-type stars. We detect Delta Ks < 5 mag companions for 20-25% of our targets with separations in the range 30-100 mas (typically, 40 - 200 A.U.). Most of these companions were unknown, shedding thus new light on the multiplicity properties of massive stars in a separation and brightness regime that has been difficult to explore so far. Adding detections from other techniques (spectroscopy, interferometry, speckle, lucky imaging, AO), the fraction of O stars with at least one companion is 85% (51/60 targets). This is the largest multiplicity fraction ever found.